#include <cstdio>
#include <cstdlib>

#include <sort.h>
#include <timer.h>
#include <random_generator.h>

#include "insert.h"
#include "merge.h"

#define ARRAY_RANDOM			0
#define ARRAY_SORTED			1
#define ARRAY_INVERSE_SORTED	2

void
print_array(hw1type* A, int l, int r)
{
	int i;
	for (i = l; i <= r; i++) 
	{
		printf("(%ld, %ld) (sum=%ld)\n", A[i].x, A[i].y, A[i].x+A[i].y);
	}
}

void
basic_test(int type)
{
	int i;
	hw1type dummy_ay[10] = {
		{13, 24}, {50, 74}, {2, 85}, {52, 15}, {0, 1},
		{78, 24}, {67, 13}, {43, 29}, {19, 1}, {25, 12}
	};

	printf("The unsorted array:\n");	
	for (i = 0; i < 10; i++) 
	{
		printf("new pair (%ld, %ld)\n", dummy_ay[i].x, dummy_ay[i].y);
		//int j, comp;
		//for (j = i - 1; j >= 0; j--)
		//{
		//	comp = compare(dummy_ay[i], dummy_ay[j]);
		//	printf("(%ld, %ld) %c (%ld, %ld)\n", 
		//		dummy_ay[i].x, dummy_ay[i].y, 
		//		((comp == 1) ? '>' : ((comp == -1) ? '<' : ((comp == 0) ? '=' : '*'))),
		//		dummy_ay[j].x, dummy_ay[j].y);
		//}
		//printf("\n");
	}
	printf("\n");

	if (type == SORT_T_INSERTION) 
	{
		printf("Using Insertion Sort ... ");
		insert_sort(dummy_ay, 0, 9);
	} else if (type == SORT_T_MERGE) {
		printf("Using Merge Sort ... \n");
		merge_sort(dummy_ay, 0, 9);	
	} else if (type == SORT_T_MERGE_INS) {
		printf("Using Merge-Insert Sort ... \n");
		merge_sort(dummy_ay, 0, 9, 3);	
	}else {
		printf("Error sort algorithm!\n");
		return;
	}

	if (check_sorted(dummy_ay, 0, 10))
	{
		printf("success.\n");
	} else {
		printf("failed.\n");
	}
	
	print_array(dummy_ay, 0, 9);
}

void
sort_evaluate(int type, int n_size, int sorted, int times, int threshold)
{
	timer		stmr, ttmr;
	hw1type*	A;
	
	if (times <= 0)
		return;

	printf("\nalgorithm=%d, type=%d, size=%d", type, sorted, n_size);
	if (type == SORT_T_MERGE_INS) 
		printf(", Threshold: %d\n", threshold);
	printf("\n");

	//ttmr.reset();
	while (times-- > 0)
	{
		//stmr.reset();
		switch (sorted) {
		case ARRAY_RANDOM:
			A = create_random_hw1type(n_size);
			break;
		case ARRAY_SORTED:
			A = create_sorted_hw1type(n_size);
			break;
		case ARRAY_INVERSE_SORTED:
			A = create_reverse_sorted_hw1type(n_size);
			break;
		}
		stmr.start();
		if (type == SORT_T_INSERTION)
			insert_sort(A, 0, n_size - 1);	
		else if (type == SORT_T_MERGE)
			merge_sort(A, 0, n_size - 1);	
		else if (type == SORT_T_MERGE_INS) 
			merge_sort(A, 0, n_size - 1, threshold);
		else
			return;
		stmr.stop();
		if (!check_sorted(A, 0, n_size))
		{
			/* We shouldn't be here */
			printf("Sort failed, evaluation will terminate!\n");
			delete A;
			return;
		}
		delete A;
		ttmr = ttmr + stmr;
	}
	ttmr = ttmr / times;
	ttmr.print();
}

void
eval_insert()
{
	int i, n_size[] = {2500, 5000, 10000, 25000, 50000, 100000, 250000};

	for (i = 0; i < sizeof(n_size) / sizeof(int); i++) 
	{
		sort_evaluate(SORT_T_INSERTION, n_size[i], ARRAY_RANDOM, 10, 0); 
		sort_evaluate(SORT_T_INSERTION, n_size[i], ARRAY_SORTED, 10, 0); 
		sort_evaluate(SORT_T_INSERTION, n_size[i], ARRAY_INVERSE_SORTED, 10, 0); 
		printf("\n");
	}
}

void
eval_merge()
{
	int i, n_size[] = {50000, 100000, 250000, 500000, 1000000, 2500000, 5000000, 10000000};

	for (i = 0; i < sizeof(n_size) / sizeof(int); i++) 
	{
		sort_evaluate(SORT_T_MERGE, n_size[i], ARRAY_RANDOM, 10, 0); 
		sort_evaluate(SORT_T_MERGE, n_size[i], ARRAY_SORTED, 10, 0); 
		sort_evaluate(SORT_T_MERGE, n_size[i], ARRAY_INVERSE_SORTED, 10, 0); 
		printf("\n");
	}
}

void
eval_merge_ins()
{
	int i, n_size[] = {50000, 100000, 250000, 500000, 1000000, 2500000, 5000000, 10000000};
	int j, k[] = {10, 50, 100, 1000};

	for (i = 0; i < sizeof(n_size) / sizeof(int); i++) 
	{
		sort_evaluate(SORT_T_MERGE_INS, n_size[i], ARRAY_RANDOM, 10, 1);
		sort_evaluate(SORT_T_MERGE_INS, n_size[i], ARRAY_SORTED, 10, 1);
		sort_evaluate(SORT_T_MERGE_INS, n_size[i], ARRAY_INVERSE_SORTED, 10, 1);
		printf("\n");

		for (j = 0; j < sizeof(k) / sizeof(int); j++) 
		{
			sort_evaluate(SORT_T_MERGE_INS, n_size[i], ARRAY_RANDOM, 10, k[j]);
			sort_evaluate(SORT_T_MERGE_INS, n_size[i], ARRAY_SORTED, 10, k[j]);
			sort_evaluate(SORT_T_MERGE_INS, n_size[i], ARRAY_INVERSE_SORTED, 10, k[j]);
			printf("\n");
		}
	}
}

//#define HW1_Q1
//#define HW1_Q2
//#define HW1_Q3
#define HW1_INPUT

int main(int argc, char* argv[])
{
	int i, j, t, a, k;
	printf("Welcome CS600 Homework #1 by Shoufu Luo. \n\n");
#ifdef HW1_Q1
	basic_test(SORT_T_INSERTION);
	basic_test(SORT_T_MERGE);
	basic_test(SORT_T_MERGE_INS);
#endif

#ifdef HW1_Q2
	printf("Sort Algorithm Evalution: \n");
	eval_insert();
	eval_merge();
#endif

#ifdef HW1_Q3
	printf("Merge-Insert Sort Algorithm Evalution: \n");
	eval_merge_ins();
#endif

#ifdef HW1_INPUT
size:
	printf("Input array size: ");
	j = scanf("%d", &i);	
	if (i < 0 || j < 0) {
		printf("Error: no negative!\n");
		goto size;
	}

type:
	printf("\nInput array type\n 0-random\n 1-sorted\n 2-inverse sorted\n: ");
	j = scanf("%d", &t);	
	if (t != 0 && t != 1 && t != 2 || j < 0)
	{
		printf("Error: incorrect type!\n");
		goto type;
	}

alg:
	printf("\nInput Sort Algorithm \n 0-insert\n 1-merge\n 2-merge_insert\n: ");
	j = scanf("%d", &a);	
	if (a != 0 && a != 1 && a != 2 || j < 0)
	{
		printf("Error: incorrect algorithm type!\n");
		goto alg;
	}

	k = 0;
	if (a == 2) 
	{
thd:
		printf("\nInput threshold k (between 1-%d): ", i);
		j = scanf("%d", &k);	
		if (k < 0 || j < 0)
		{
			printf("Error, no negative!\n");
			goto thd;
		}
	}
	
	sort_evaluate(a, i, t, 10, k);
	printf("\n\n");
#endif
	
	return 0;
}

